package com.cty.A_GeneralDataStructures.C_Tree.BinaryTree;

import com.cty.F_common.DataItem;

import java.util.Stack;

/**
 * @Auther: cty
 * @Date: 2020/6/15 22:17
 * @Description: 普通二叉搜索树
 * 应用场景：
 *      当数据量大时，考虑哈希表或树
 *          当数据量不可预测时，考虑树
 *              当数据是随机输入时，考虑普通二叉搜索树（非平衡树）
 * 重要操作：
 *      ① find(long): DataItem    O(logN)
 *      ② insert(DataItem): void    O(logN)
 *      ③ delete(long): DataItem    O(logN)
 *      ④ traverse(int): void    O(N)
 *      ⑤ displayTree(): void
 * @version: 1.0
 */
public class BinaryTree {
    private Node root;

    public BinaryTree(){
        root = null;
    }

    /**
     * 查找  O(logN)
     * @param key
     * @return
     */
    public DataItem find(long key){
        // 查找
        Node current = root;

        while(current!=null && current.data.getKey()!=key){
            if(key < current.data.getKey())
                current = current.leftChild;
            else
                current = current.rightChild;
        }

        // 处理查找结果
        if(current == null)
            return null;  // 不存在关键字为key的节点
        else
            return current.data;  // 查找成功
    }  // end find()

    /**
     * 插入  O(logN)
     * @param item
     */
    public void insert(DataItem item){
        Node newNode = new Node(item);

        if(root == null) {
            root = newNode;  // 空树
            return;
        }

        // 查找
        Node current = root;
        Node parent = null;
        boolean isLeftChild = true;

        while(current != null){
            parent = current;

            if(item.getKey() < current.data.getKey()){
                current = current.leftChild;
                isLeftChild = true;
            }else{
                current = current.rightChild;
                isLeftChild = false;
            }
        }

        // 处理查找结果
        if(isLeftChild)
            parent.leftChild = newNode;
        else
            parent.rightChild = newNode;
    }  // end insert()

    /**
     * 删除  O(logN)
     * @param key
     * @return
     */
    public DataItem delete(long key){
        // 查找
        Node newNode = new Node(new DataItem(key));
        Node current = root;
        Node parent = null;
        boolean isLeftChild = true;

        while(current!=null && current.data.getKey()!=key){
            parent = current;

            if(key < current.data.getKey()){
                current = current.leftChild;
                isLeftChild = true;
            }else{
                current = current.rightChild;
                isLeftChild = false;
            }
        }

        // 处理查找结果
        if(current == null)
            return null;  // 空树或不存在关键字为key的节点

        // 若查找到待删除节点
        if(current.leftChild == null && current.rightChild==null)   // ① 待删除节点是叶子节点
            if(current == root)  // 待删除节点是根节点
                root = null;
            else if(isLeftChild)  // 待删除节点是父节点的左子节点
                parent.leftChild = null;
            else  // 待删除节点是父节点的右子节点
                parent.rightChild = null;
        else if(current.rightChild == null)  // ② 待删除节点只有左子节点
            if(current == root)
                root = current.leftChild;
            else if(isLeftChild)
                parent.leftChild = current.leftChild;
            else
                parent.rightChild = current.leftChild;
        else if(current.leftChild == null)  // ③ 待删除节点只有右子节点
            if(current == root)
                root = current.rightChild;
            else if(isLeftChild)
                parent.leftChild = current.rightChild;
            else
                parent.rightChild = current.rightChild;
        else{  // ④ 待删除节点有两个子节点
            Node successor = getSuccessor(current);  // 获取后继节点
            if(current == root)
                root = successor;
            else if(isLeftChild)
                parent.leftChild = successor;
            else
                parent.rightChild = successor;
            successor.leftChild = current.leftChild;  // 将待删除节点的左子节点设置为后继节点的左子节点
        }
        return current.data;  // 返回查找到的待删除节点
    }  // end delete()

    /**
     * 获取当前节点的后继节点
     * @return
     */
    private Node getSuccessor(Node delNode){
        // 查找
        Node successorParent = delNode;
        Node successor = delNode.rightChild;
        Node current = successor.leftChild;

        while(current != null){
            successorParent = successor;
            successor = current;
            current = current.leftChild;
        }

        // 处理查找结果
        if(successor != delNode.rightChild){  // 若后继节点不是待删除节点的右子节点
            successorParent.leftChild = successor.rightChild;  // 将后继节点的右子节点移到后继节点父节点的左子节点
            successor.rightChild = delNode.rightChild;  // 待删除节点的右子节点移到后继节点的右子节点
        }
        return successor;
    }

    /**
     * 遍历
     * @param type
     */
    public void traverse(int type){
        switch (type){
            case 1:
                preOrder(root);
                break;
            case 2:
                inOrder(root);
                break;
            case 3:
                postOrder(root);
                break;
            default:
                System.out.println("Invalid enter");
        }
        System.out.println();
    }

    /**
     * 前序遍历
     * @param current
     */
    private void preOrder(Node current){
        if(current != null){
            current.data.displayItem();
            preOrder(current.leftChild);
            preOrder(current.rightChild);
        }
    }

    private void inOrder(Node current){
        if(current != null){
            inOrder(current.leftChild);
            current.data.displayItem();
            inOrder(current.rightChild);
        }
    }

    private void postOrder(Node current){
        if(current != null){
            postOrder(current.leftChild);
            postOrder(current.rightChild);
            current.data.displayItem();
        }
    }

    /**
     * 显示树
     */
    public void displayTree()
    {
        Stack globalStack = new Stack();
        globalStack.push(root);
        int nBlanks = 32;
        boolean isRowEmpty = false;
        System.out.println("..........................................................................");

        while(!isRowEmpty)
        {
            Stack localStack = new Stack();
            isRowEmpty = true;

            for(int i=0; i<nBlanks; i++)
                System.out.print(' ');

            while(!globalStack.empty())
            {
                Node temp = (Node)globalStack.pop();
                if(temp != null)
                {
                    System.out.print(temp.data.getKey());
                    localStack.push(temp.leftChild);
                    localStack.push(temp.rightChild);

                    if(temp.leftChild!=null || temp.rightChild!=null)
                        isRowEmpty = false;
                }
                else
                {
                    System.out.print("--");
                    localStack.push(null);
                    localStack.push(null);
                }

                for(int i=0; i<nBlanks*2-2; i++)
                    System.out.print(' ');
            }  // end while !globalStack.empty()

            System.out.println();
            nBlanks /= 2;
            while(!localStack.isEmpty())
                globalStack.push(localStack.pop());
        }  // end while !isRowEmpty

        System.out.println("..........................................................................");
    }  // end displayTree()

}  // end BinaryTree{}
